package com.moyoutian.leetcode;

/**
 * 35. 搜索插入位置
 * <p>
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * <p>
 * 请必须使用时间复杂度为 O(log n) 的算法。
 */
public class Demo35 {

    public static void main(String[] args) {

        int[] ints = new int[]{1, 2, 5, 9};
        System.out.println(searchInsert(ints, 9));
    }

    public static int searchInsert(int[] nums, int target) {
        return searchInsert(nums, target, 0, nums.length - 1);
    }

    /**
     * 查找目标值放的位置
     *
     * @param nums   数组
     * @param target 目标值
     * @param l      当前左下标
     * @param r      当前右下标
     * @return 目标值放的位置下标
     */
    public static int searchInsert(int[] nums, int target, int l, int r) {
        int tempIndex = l + ((r - l) / 2);
        if (l <= r) {
            if (nums[tempIndex] == target) {
                return tempIndex;
            }
            //最左边的情况
            else if (nums[tempIndex] > target && tempIndex == l) {
                return tempIndex;
            }
            // 先判断最右边的情况，这一定要放在中间点之前，要不然中间点有可能数组越界
            else if (nums[tempIndex] < target && tempIndex == r) {
                return tempIndex + 1;

                //在俩数中间的情况
            } else if (nums[tempIndex] < target && target < nums[tempIndex + 1]) {
                return tempIndex + 1;

                //递归处理的情况
            } else if (target > nums[tempIndex]) {
                return searchInsert(nums, target, tempIndex + 1, r);
            } else {
                return searchInsert(nums, target, l, tempIndex - 1);
            }
        }
        return -1;
    }

}
